class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n=s.size();
        int left=0;
        int right=n;
        vector<int> ret;
        for(int i=0;i<n;++i)
        {
            if(s[i]=='I')
            {
                ret.push_back(left++);
            }
            else if(s[i]=='D')
            {
                ret.push_back(right--);
            }
        }
        ret.push_back(left);
        return ret;
    }
};
